package 字符串接龙;

import java.util.*;

/**
 * @author: AirMan
 * @date: 2025/6/4 10:22
 * @description:
 * 题目描述
 * 字典 strList 中从字符串 beginStr 和 endStr 的转换序列是一个按下述规格形成的序列：
 * 序列中第一个字符串是 beginStr。
 * 序列中最后一个字符串是 endStr。
 * 每次转换只能改变一个位置的字符（例如 ftr 可以转化 fty ，但 ftr 不能转化 frx）。
 * 转换过程中的中间字符串必须是字典 strList 中的字符串。
 * beginStr 和 endStr 不在 字典 strList 中
 * 字符串中只有小写的26个字母
 * 给你两个字符串 beginStr 和 endStr 和一个字典 strList，找到从 beginStr 到 endStr 的最短转换序列中的字符串数目。如果不存在这样的转换序列，返回 0。
 * 输入描述
 * 第一行包含一个整数 N，表示字典 strList 中的字符串数量。 第二行包含两个字符串，用空格隔开，分别代表 beginStr 和 endStr。 后续 N 行，每行一个字符串，代表 strList 中的字符串。
 * 输出描述
 * 输出一个整数，代表从 beginStr 转换到 endStr 需要的最短转换序列中的字符串数量。如果不存在这样的转换序列，则输出 0。
 * 输入示例
 */
public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String beginStr = sc.next();
        String endStr = sc.next();
        sc.nextLine();
        List<String> wordList = new ArrayList<>();
        wordList.add(beginStr);
        wordList.add(endStr);
        for (int i = 0; i < n; i++) {
            wordList.add(sc.nextLine());
        }
        int count = bfs(beginStr, endStr, wordList);
        System.out.println(count);
    }

    // 采用 bfs 算法，如何判断一个字符串能够抵达另一个字符串呢？如果替换前者中的一个字符，能够和它相等，就说明可达
    // 也就说明了这两个节点可连接。那我们又如何判断一个节点是否访问过呢？通过一个set集合，如果一个字符串出现过
    // 就说明这个节点已经被访问过了
    private static int bfs(String beginStr, String endStr, List<String> wordList) {
        Deque<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>(); // Set存放访问节点，也是方便我们查看一个字符串是否出现在里面
        Set<String> set = new HashSet<>(wordList); // Set存放，方便我们判断一个字符是否出现在字典中
        int len = 1;
        queue.add(beginStr); // 以 beginStr 为开始节点
        visited.add(beginStr);
        while (!queue.isEmpty()) {
            int levelSize = queue.size(); // 一层只能够使路径加一，不能通过遍历charArray判断，因为一层需要遍历所有节点
            for (int k = 0; k < levelSize; k++) {
                String node = queue.poll();
                char[] charArray = node.toCharArray();
//                boolean flag = false; // (这是错误方法)用来标记以node为开始，扩展一层，是否能够找到一条新路径
                for (int i = 0; i < charArray.length; i++) {
                    char old = charArray[i]; // 存放修改的值，用于回溯
                    for (char j = 'a'; j <= 'z'; j++) {
                        charArray[i] = j;
                        String newStr = new String(charArray);
                        // 如果字符串等于 endStr，说明已经到终点了
                        if (newStr.equals(endStr)) {
                            return set.contains(endStr) ? len + 1 : 0; // endStr也必须在字典中
                        } else if (set.contains(newStr) && !visited.contains(newStr)) {
//                            flag = true; // 错误方法
                            // 如果字典包含这个字符串，并且没有被访问过，说明我们找到了两个节点相连的一条新路径
                            queue.add(newStr);
                            visited.add(newStr);
                        }
                    }
                    charArray[i] = old; // 回溯
                }
            }
            len++; // 当前层的所有节点遍历完毕。len+1，如果当前层没有扩展到节点，那么while循环将推出，返回0
            // 如果当前层扩展到节点了，那么len+1也是理应的
        }
        return 0;
    }
}
